//给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以
//穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。 
//
// 给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 
//10⁹ + 7 取余 后的结果。 
//
// 
//
// 示例 1： 
//
// 
//输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
//输出：6
// 
//
// 示例 2： 
//
// 
//输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
//输出：12
// 
//
// 
//
// 提示： 
//
// 
// 1 <= m, n <= 50 
// 0 <= maxMove <= 50 
// 0 <= startRow < m 
// 0 <= startColumn < n 
// 
// Related Topics动态规划 
//
// 👍 262, 👎 0 
//
//
//
//

package leetcode.editor.cn;

class OutOfBoundaryPaths {
    public static void main(String[] args) {
        Solution solution = new OutOfBoundaryPaths().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 记忆化dfs
        Integer[][][] cache;
        int mod = (int) 1e9 + 7;
        int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
            cache = new Integer[m][n][maxMove + 1];
            return dfs(m, n, startRow, startColumn, maxMove);
        }

        public int dfs(int m, int n, int x, int y, int move) {
            if (x < 0 || y < 0 || x >= m || y >= n) return 1;

            if (move == 0) return 0;

            if (cache[x][y][move] != null) return cache[x][y][move];

            int cnt = 0;
            for (int[] d : dir) {
                cnt += dfs(m, n, x + d[0], y +d[1], move -1);
                cnt %= mod;
            }

            cache[x][y][move] = cnt;

            return cnt;
        }


        // 路径dp
        // https://leetcode.cn/leetbook/read/path-problems-in-dynamic-programming/r8doce/
        /*int m, n, N;
        int mod = (int) 1e9 + 7;

        public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
            this.m = m;
            this.n = n;
            this.N = maxMove;

            // 表示从i开始，移动j步到达目的地的路径数
            int[][] dp = new int[m * n][N + 1];

            // 对边界进行初始化
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0) add(i, j, dp);
                    if (i == m - 1) add(i, j, dp);
                    if (j == 0) add(i, j, dp);
                    if (j == n - 1) add(i, j, dp);
                }
            }

            int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (int i = 1; i <= maxMove; i++) {
                for (int j = 0; j < m * n; j++) {
                    // 计算坐标
                    int[] arr = parseIdx(j);
                    for (int[] d : dir) {
                        int x = arr[0] + d[0], y = arr[1] + d[1];

                        if (x >= 0 && y >= 0 && x < m && y < n) {
                            int idx = getIndex(x, y);
                            dp[j][i] += dp[idx][i - 1];
                            dp[j][i] %= mod;
                        }
                    }
                }
            }

            return dp[getIndex(startRow, startColumn)][maxMove];
        }

        public int getIndex(int i, int j) {
            return i * n + j;
        }

        public int[] parseIdx(int idx) {
            return new int[]{idx / n, idx % n};
        }

        public void add(int i, int j, int[][] dp) {
            for (int k = 1; k <= N; k++) {
                dp[getIndex(i, j)][k]++;
            }
        }*/

    }
//leetcode submit region end(Prohibit modification and deletion)

}
